function addTranglesIntoList(list, patch, max){
	var temp = [];
	for(var i = 0; i <patch.data.length/2; i++){
		var tempPoint = changeCoordinatePoint3({x:patch.data[i*2], y:patch.data[i*2+1], z:0}, patch.coordinate,normalCoordinate);
		//var tempPoint = {x:patch.data[i*2], y:patch.data[i*2+1], z:0};
		temp.push(tempPoint.x/max);
		temp.push(tempPoint.y/max);
		temp.push(tempPoint.z/max);
	}
	if(patch.data.length < 3*2){
		return;
	}
	for(var i = 0; i < patch.data.length/2; i++){
		list.push(temp[i*3+0]);
		list.push(temp[i*3+1]);
		list.push(temp[i*3+2]);
		list.push(temp[((i+1)%(patch.data.length/2))*3+0]);
		list.push(temp[((i+1)%(patch.data.length/2))*3+1]);
		list.push(temp[((i+1)%(patch.data.length/2))*3+2]);
	}
}
function createTrianglesWithModel(model, normalMax){
	var retTrangles = [];
	for(var i = 0; i < model.patches.length; i++){
		addTranglesIntoList(retTrangles, model.patches[i], normalMax);
	}
	return retTrangles;
}

function createPatchVertices (patch) {
	if (patch.data.length < 3 * 2) {
		return null;
	}
	var result = { vertices: [], indices: [] };
	var vertexCount = patch.data.length / 2;
	for (var i = 0; i < vertexCount; i++) {
		var p = changeCoordinatePoint3(
			{ x:patch.data[i*2], y:patch.data[i*2+1], z:0 },
			patch.coordinate, normalCoordinate
		);
		result.vertices.push(p.x);
		result.vertices.push(p.y);
		result.vertices.push(p.z);
	}
	for (var i = 1; i < vertexCount - 1; ++i) {
		result.indices.push(0);
		result.indices.push(i);
		result.indices.push(i + 1);
	}
	result.color = patch.color;
	return result;
}

function createModelVertices (model) {
	var info = [];
	for (var i = 0; i < model.patches.length; i++) {
		info.push(createPatchVertices(model.patches[i]));
	}
	return info;
}

function isPointInPatch(x, y, patch) {
	var vertexCount = patch.data.length / 2;
	var result = false;
	var last = vertexCount - 1;
	var x1, y1;
	var x2 = patch.data[last*2], y2 = patch.data[last*2+1];
	for (var i = 0; i < vertexCount; ++i) {
		var x1 = patch.data[i*2];
		var y1 = patch.data[i*2+1];
		if ((y1 > y) != (y2 > y) &&
			x < (x2 - x1) / (y2 - y1) * (y - y1) + x1) {
			result = !result;
		}
		x2 = x1;
		y2 = y1;
	}
	return result;
}

function distance(x1, y1, x2, y2) {
	return Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

function dot(x1, y1, x2, y2) {
	return x1 * x2 + y1 * y2;
}

function pointToEdgeDistance(x, y, ux, uy, vx, vy) {
	if (Math.abs(ux - vx) < 0.5 && Math.abs(uy - vy) < 0.5) {
		return distance(x, y, ux, uy);
	}
	var dx = vx - ux;
	var dy = vy - uy;
	var t = dot(x - ux, y - uy, vx - ux, vy - uy) / dot(dx, dy, dx, dy);
	if (t < 0.0) {
		return distance(x, y, ux, uy);
	}
	else if (t > 1.0) {
		return distance(x, y, vx, vy);
	}
	var projectionX = ux + t * dx;
	var projectionY = uy + t * dy;
	return distance(x, y, projectionX, projectionY);
}

function findHitEdge(x, y, patch, epsilon) {
	var vertexCount = patch.data.length / 2;
	var last = vertexCount - 1;
	var x1, y1;
	var x2 = patch.data[last*2], y2 = patch.data[last*2+1];
	var min = Number.MAX_VALUE;
	var index = -1;
	for (var i = 0; i < vertexCount; ++i) {
		var x1 = patch.data[i*2];
		var y1 = patch.data[i*2+1];
		var d = pointToEdgeDistance(x, y, x1, y1, x2, y2);
		if (d < epsilon && d <= min) {
			min = d;
			index = i;
		}
		x2 = x1;
		y2 = y1;
	}
	if (index < 0) {
		return null;
	}
	var end = { x: patch.data[index*2], y: patch.data[index*2+1], z: 0 };
	index = (index - 1 + vertexCount) % vertexCount;
	var start = { x: patch.data[index*2], y: patch.data[index*2+1], z: 0 };
	return { start: start, end: end };
}

function findHitVertex(x, y, patch, epsilon) {
	var vertexCount = patch.data.length / 2;
	for (var i = 0; i < vertexCount; ++i) {
		var vx = patch.data[i*2];
		var vy = patch.data[i*2+1];
		if (Math.abs(x - vx) < epsilon && Math.abs(y - vy) < epsilon) {
			return { x: vx, y: vy, z: 0 };
		}
	}
	return null;
}

function perpendicularBisector(x1, y1, x2, y2) {
	var line = { start: {}, end: {} };
	var mx = (x1 + x2) / 2;
	var my = (y1 + y2) / 2;
	var dx = y1 - y2;
	var dy = x2 - x1;
	line.start.x = mx + dx;
	line.start.y = my + dy;
	line.start.z = 0;
	line.end.x = mx - dx;
	line.end.y = my - dy;
	line.end.z = 0;
	return line;
}

// [Reference] http://en.wikipedia.org/wiki/Line-line_intersection
function intersect(edge1, edge2) {
	var x1 = edge1.start.x;
	var y1 = edge1.start.y;
	var x2 = edge1.end.x;
	var y2 = edge1.end.y;
	var x3 = edge2.start.x;
	var y3 = edge2.start.y;
	var x4 = edge2.end.x;
	var y4 = edge2.end.y;

	var dx12 = x1 - x2;
	var dx34 = x3 - x4;
	var dy12 = y1 - y2;
	var dy34 = y3 - y4;

	var denominator = dx12 * dy34 - dy12 * dx34;
	if (Math.abs(denominator) < 1e-2) {
		return null;
	}

	var point = {};
	var c12 = x1 * y2 - y1 * x2;
	var c34 = x3 * y4 - y3 * x4;
	point.x = (c12 * dx34 - c34 * dx12) / denominator;
	point.y = (c12 * dy34 - c34 * dy12) / denominator;
	point.z = 0;
	return point;
}

function projection(point, edge) {
	var dx = edge.end.x - edge.start.x;
	var dy = edge.end.y - edge.start.y;
	var dxdx = dx * dx;
	var dxdy = dx * dy;
	var dydy = dy * dy;
	var n = dxdx + dydy;
	var px = dxdx * point.x + dxdy * point.y;
	var py = dxdy * point.x + dydy * point.y;
	var ox = dydy * edge.start.x - dxdy * edge.start.y;
	var oy = dxdx * edge.start.y - dxdy * edge.start.x;
	return { x: (px+ox)/n, y: (py+oy)/n, z: 0 };
}

function edgesBisector(edge1, edge2) {
	var x1 = edge1.start.x;
	var y1 = edge1.start.y;
	var x2 = edge1.end.x;
	var y2 = edge1.end.y;
	var x3 = edge2.start.x;
	var y3 = edge2.start.y;
	var x4 = edge2.end.x;
	var y4 = edge2.end.y;

	var intersection = intersect(edge1, edge2);
	if (!intersection) { // two lines are parallel
		var s, e;
		if (dot(x2 - x1, y2 - y1, x4 - x3, y4 - y3) > 0) {
			s = { x: (x1+x3)/2, y: (y1+y3)/2, z: 0 };
			e = { x: (x2+x4)/2, y: (y2+y4)/2, z: 0 };
		}
		else {
			s = { x: (x1+x4)/2, y: (y1+y4)/2, z: 0 };
			e = { x: (x2+x3)/2, y: (y2+y3)/2, z: 0 };
		}
		return { start: s, end: e };
	}
	var ix = intersection.x;
	var iy = intersection.y;

	var d1 = distance(ix, iy, x1, y1);
	var d2 = distance(ix, iy, x2, y2);
	var d3 = distance(ix, iy, x3, y3);
	var d4 = distance(ix, iy, x4, y4);

	var t = Math.max(d1, d2, d3, d4) * 2;

	var px1, py1, px2, py2;
	if (d1 >= d2) {
		px1 = ix + (x1 - ix) / d1 * t;
		py1 = iy + (y1 - iy) / d1 * t;
	}
	else {
		px1 = ix + (x2 - ix) / d2 * t;
		py1 = iy + (y2 - iy) / d2 * t;
	}
	if (d3 >= d4) {
		px2 = ix + (x3 - ix) / d3 * t;
		py2 = iy + (y3 - iy) / d3 * t;
	}
	else {
		px2 = ix + (x4 - ix) / d4 * t;
		py2 = iy + (y4 - iy) / d4 * t;
	}
	return { start: intersection, end: { x: (px1+px2)/2, y: (py1+py2)/2, z: 0 } };
}
